COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00061 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a15.tex[254,mps] \today\hfill}
\line{\copyright July 6, 1984 Robert W. Floyd\hfill}

\bigskip
\noindent
{\bf Cartesian Products and Ordered Pairs.}

\bigskip\noindent
[This note was prepared by gluing three separately written ones together.
Redundancies abound. Sorry.]

\bigskip

We use certain boldface capital letters as names for certain sets repeatedly
encountered. The set of integers is~{\bf Z} (German zahl $=$ number).
The set of natural numbers (non-negative integers) is~{\bf N}. The set
of positive (nonzero) integers is~{\bf N}$↓+$. The set of rational
numbers is~{\bf Q} (quotient). The set of real numbers is~{\bf R}.
In handwriting, these symbols are doubly underlined.

If $X$ and $Y$ are sets, the {\it cartesian product\/} $X\times Y$ is a set,
each of whose elements is made from an element~$x$ of~$X$ and an element~$y$
of~$Y$ in such a way that they can be recovered. The element of $X\times Y$
made from $x$ and~$y$ is called the {\sl ordered pair\/}
$\langle x,y\rangle$. The axioms are:
$$\eqalign{X\times Y&=\{\,\langle x,y\rangle\mid x\in X,y\in Y\,\}\,.\cr
\langle x↓1,y↓1\rangle&=\langle x↓2,y↓2\rangle \supset x↓1=x↓2,y↓1=y↓2\,.\cr}$$
Implicitly, there are {\it projection functions\/} 
$\pi↓1$ and $\pi↓2$ such that
$\langle x,y\rangle\pi↓1=x$, $\langle x,y\rangle\pi↓2=y$.

Numerous systems satisfy these axioms.

\smallskip
\disleft 25pt:(1):
Let $X$ and $Y$ be $N$. Let $\langle x,y\rangle =2↑x(2y+1)$
and $\pi↓1(z)=$ exponent of~2 in the prime factorization of~$z$,
$\pi↓2(z)=\bigl(z/\pi↓1(z)-1\bigr)/2$.
In this case, $X\times Y$ is also~$N$.

\smallskip
\disleft 25pt:(2):
Let $X$ and $Y$ be any subsets of $N$, and $\langle x,y\rangle$,
$\pi↓1(z)$, $\pi↓2(z)$ as above.

\smallskip
\disleft 25pt:(3):
Let $X=\{1,2,3\}$, $Y=\{0,1\}$, and $\langle x,y\rangle=10x+y$ (or the
decimal numeral representing that number); e.g., $\langle 2,1\rangle =21$.

\smallskip
\disleft 25pt:(4):
Let $X$ and $Y$ be the set of decimal numerals. Let $\langle x,y\rangle$
be the character string obtained by writing~``$\langle$'', then the digits
of~$x$, then a comma, then the digits of~$y$, then~``$\rangle$''.
In this case the formula for an ordered pair (say, ``$\langle 13,169\rangle$'')
is identical to the object it names. This is an example of a method due to
Herbrand of constructing functions whose outputs show what function was
applied, and to which arguments.

\smallskip
\disleft 25pt:(5):
Let $X$ and $Y$ be the set of lists as defined in LISP. Let $\langle x,y\rangle
=\hbox{CONS}(x,y)$, $\pi↓1(z)=\hbox{CAR}(z)$, 
$\pi↓2(z)=\hbox{CDR}(z)$, and $X\times Y$ is the set of non-atomic lists.

\smallskip
\disleft 25pt:(6):
Let $X=Y=N$. Let $\langle x,y\rangle =2↑x\cdot 3↑y$; this type of
ordered pair function was used by Kurt G\"odel.

\smallskip
If $X=Y=X\times Y$, $\langle x,y\rangle$ is customarily called a pairing
function.

\smallskip
\disleft 38pt::
{\bf Drill:} Show $(X↓1\subseteq X↓2∧Y↓1\subseteq Y↓2)\equiv (X↓1\times Y↓1\subseteq
X↓2\times Y↓2)$; $|X\times Y|=|X|\times |Y|$;
$\langle x↓1,\langle y↓1,z↓1\rangle\rangle 
=\langle x↓2,\langle y↓2,z↓2\rangle\rangle$
implies $x↓1=x↓2$, $y↓1=y↓2$, $z↓1=z↓2$.

\bigskip
In a similar way, we can define the cartesian product of three or more sets
$X↓1\times X↓2\times \cdots\times X↓n=\{\langle x↓1,x↓2,\ldots,x↓n\rangle\}$,
where $\langle x↓1,x↓2,\ldots,x↓n\rangle =\langle y↓1,y↓2,\ldots,y↓n\rangle$
only if for each~$i$, $x↓i=y↓i$. For logical completeness, we allow
ordered 1-tuples~$\langle x\rangle$, and the ordered 0-tuple~$\langle\,\rangle$,
also known as $\Lambda$.

\bigskip
\noindent{\bf Sequences and Strings.}

If $X$ is a set, let $X↑0=\{\langle\,\rangle\}$, 
$X↑1=\{\,\langle x\rangle\mid x\in X\,\}$,
$X↑2=\{\,\langle x↓1,x↓2\rangle\mid x↓1,x↓2\in X\,\}$,
etc., where the $X↑i$ are disjoint.
Let $X↑{\ast}$, the set of {\sl sequences\/} over~$X$, be
$\bigcup↓{i≥0}X↑i$,
$X↑+=\bigcup↓{i≥1}X↑i$. The operation of concatenation, $\otimes$,
is defined on sequences:
$$\eqalign{&\langle x↓1,x↓2,\ldots,x↓a\rangle\otimes\langle y↓1,y↓2,\ldots,y↓b\rangle
=\cr
&\langle x↓1,x↓2,\ldots,x↓a,y↓1,y↓2,\ldots,y↓b\rangle\,.\cr}$$

\smallskip
\disleft 38pt::
{\bf Drill:} 
$$\eqalign{\Lambda\otimes u&=u=u\otimes\Lambda\cr
|u\otimes v|&=|u|+|v|\,.\cr}$$

\smallskip
If $X$ is a finite set, often we will call it an {\sl alphabet\/}, its elements
{\sl characters\/}, and elements of $X↑{\ast}$ {\sl strings\/} over~$X$.
Usually
if $X$ is the alphabet of a natural language, $\langle x↓1,x↓2,\ldots,x↓a\rangle$
can be defined to be the result of writing $x↓1$, $x↓2$, etc., from
left to right. Exceptions may arise in cursive writing, where Dijkstra
can't be distinguished from D\"ykstra.
Fortunately, the pronunciation is the same.

If $b\in X$, define a function $S↓b$ on $X↑{\ast}$ by
$S↓b(\langle a↓1,a↓2,\ldots,a↓n\rangle)=\langle a↓1,a↓2,\ldots,a↓n,b\rangle$.
Then every sequence in $X↑{\ast}$ can be constructed by starting with
$\Lambda$ and repeatedly using some $S↓b$ to append another element.
A~standard method to prove $P(x)$ (``$x$~has property~$P$'')
for all $x\in X↑{\ast}$ is to show
$P(\Lambda)$, and to show that if $u\in X↑{\ast}$, $P(u)$, and $b\in X$,
then $P\bigl(S↓b(u)\bigr)$. This is the method of
{\sl mathematical induction\/} on sequence length.

\vfill\eject

%\bigskip
\line{\sevenrm a13.tex[154,phy] \hfil}

[This is the first page only, the rest of the file is at the end before
the added a57. A13.tex has been deleted.]

\def\aot{\buildrel\rightarrow\over\otimes}%→  over \otimes 

\bigskip

\noindent{\bf String Axioms.}

An {\it alphabet\/} (usually called $\Sigma$) is a set, finite unless
otherwise stated, whose elements are called {\it characters\/}, or
occasionally symbols. {\it Strings\/} (over $\Sigma$) are finite
sequences of characters. The set of all strings over $\Sigma$ is
called~$\Sigma↑{\ast}$. A~physical realization of these definitions
must allow for distinguishing characters in all string contexts. The
axioms for strings are analogous to the Peano axioms for integers:

$$\vcenter{\halign{$\lft{#}\qquad$&\lft{#}\cr
\qquad\hbox{Integers}&\qquad Strings\cr
\noalign{\smallskip}
0\in N&\quad $\Lambda\in\Sigma↑{\ast}$\cr
&(the empty string $\Lambda$ is the empty sequence)\cr
x\in N⊃S(x)\in N&For each $a\in\Sigma$,\cr
&\quad $x\in\Sigma↑{\ast}⊃S↓a(x)\in\Sigma↑{\ast}$\cr
S(x)≠0&$S↓a(x)≠\Lambda$\cr
x≠y⊃S(x)≠S(y)&$x≠y⊃S↓a(x)≠S↓b(y)$\cr
&$a≠b⊃S↓a(x)≠S↓b(y)$\cr
\bigl(P(0)∧\bigl(\forall x.P(x)⊃P\bigl(S(x)\bigr)\bigr)\bigr)
&$P(\Lambda)∧\bigl(\forall x,a.P(x)⊃P\bigl(S↓a(x)\bigr)\bigr)$\cr
\qquad ⊃\forall x.P(x)&$\qquad ⊃\forall x\,P(x)$\cr
\noalign{\smallskip}
\hbox{I.e., there are no ``infinite''}&I.e., there are no ``infinite''\cr
\hbox{integers; all can be reached from}&strings.\cr
\hbox{zero in finitely many steps.}\cr}}$$

\smallskip
A {\it language\/} $L$ over $\Sigma$ is a subset of $\Sigma↑{\ast}$. It may
be empty, finite, infinite, etc. Languages over $\Sigma$ include~$\emptyset$,
the empty language; $\{\Lambda\}$,~the language containing only the
empty string, often abbreviated to~$\Lambda$ when no confusion can occur;
and $\Sigma↑{\ast}$ itself.

\bigskip
\noindent{\bf Relations.}

A {\sl relation\/} $\rho$ from set $A$ to set $B$ is a predicate
$\rho(x,y)$, defined (true or false) for $x\in A$ and $y\in B$. We call
$A$ the {\it domain\/} and $B$ the {\sl range\/}. We usually write $x\rho y$ 
as a short form of $\rho(x,y)$.

Let $\rho↓1$ be a relation from $A$ to $B$, $\rho↓2$ a relation from $B$ to~$C$,
$S↓1\subseteq A$, $S↓2\subseteq C$. We define the set
$S↓1\circ \rho↓1$, the
{\it image\/} of $S↓1$ under~$\rho↓1$, as
$\{\,y\mid(\exists x)(x\in S↓1,x\rho↓1y)\,\}$.
We define the set $\rho↓2\circ S↓2$, the {\it inverse image\/} 
of $S↓2$ under~$\rho↓2$, as
$\{\,x\mid(\exists y)(y\in S↓2,x\rho↓2y)\,\}$.
We define the relation
$\rho↓1\circ \rho↓2$ by $x(\rho↓1\circ \rho↓2)z$ if
$(\exists y)(x\rho↓1y∧y\rho↓2z)$. If $S↓3$ and $S↓4$ are sets, we define
$S↓3\circ S↓4$ as a predicate, true if $(\exists x)(x\in S↓3∧x\in S↓4)$.

\smallskip
\disleft 38pt::
{\bf Drill:} Show
$$\eqalign{(S↓1\circ \rho↓1)\circ \rho↓2&=S↓1\circ (\rho↓1\circ \rho↓2)\,;\cr
(\rho↓1\circ \rho↓2)\circ \rho↓3&=\rho↓1\circ (\rho↓2\circ \rho↓3)\,;\cr
(\rho↓1\circ \rho↓2)\circ S↓2&=\rho↓1\circ (\rho↓2\circ S↓2)\,;\cr
(S↓1\circ \rho↓1)\circ S↓2&=S↓1\circ (\rho↓1\circ S↓2)\,.\cr}$$
Warning: Do not assume
$S↓1\circ (S↓2\circ \rho↓1)=(S↓1\circ S↓2)\circ \rho↓1$; the latter is not even
defined.

\smallskip
If $\rho$ is a relation from $A$ to $B$, $\rho↑{-1}$ is a relation,
called the {\it converse\/} of~$\rho$, from $B$ to~$A$
defined by $y\rho↑{-1}x$ iff $x\rho y$.

\smallskip
\disleft 38pt::
{\bf Drill:} $(\rho↑{-1})↑{-1}=\rho$. $S\circ \rho=\rho↑{-1}\circ S$.

\smallskip
A relation $\rho$ from $A$ to $B$ can be associated in a natural way with
a subset of $A\times B$, namely $X↓{\rho}=\{\,\langle a,b\rangle\mid a\rho b\,\}$.
There is no particular harm in actually identifying the relation with the
set of ordered pairs, and doing so provides us with useful extensions
of set notation: $\emptyset$~is the relation for which $x\emptyset y$
is always false, $A\times B$ is the relation from $A$ to~$B$ which is
always true, $\rho↓1\cap \rho↓2$ is the relation $x(\rho↓1\cap \rho↓2)y$ iff
$(x\rho↓1y∧x\rho↓2y)$, similarly $x(\rho↓1\cup \rho↓2)y$ iff $x\rho↓1y∨x\rho↓2y$, 
$x{\bar \rho}↓1y$ iff not $x\rho↓1y$, etc.

If $\rho$ is a relation on $A$, $\rho↑0=\{\,\langle x,x\rangle\mid x\in A\,\}=\gamma↓A$;
$\rho↑{i+1}=\rho↑i\circ \rho$, so that $\rho↑1=\rho$, $\rho↑2=\rho\circ \rho$. 
Define $\rho↑{\ast}=\bigcup↓{i≥0}\rho↑i$, $\rho↑+=\bigcup↓{i≥1}\rho↑i$.

\smallskip
\disleft 38pt::
{\bf Drill:}
$\rho↑o\circ \rho↑k=\rho↑{i+j}$ ($i,j≥0$).

\smallskip
\disleft 38pt::
{\bf Drill:}
$(\rho↑{-1})↑i=(\rho↑i)↑{-1}$ ($i≥0$), so both may be called $\rho↑{-i}$.

\smallskip
\disleft 38pt::
{\bf Drill:}
$\rho↑{i-j}$ may be different from $\rho↑i\circ (\rho↑{-j})↑{-1}$. (Try 
$\rho=\{\,\langle x,y\rangle\mid x=y∨x+1=y\,\}$.)

\smallskip
\noindent{\bf Exercise:} 
Let $X$ be a set, $\rho↓1$ and $\rho↓2$ relations.
Is $\rho↓1\circ (X\circ \rho↓2)$ always equal to $(\rho↓1\circ X)\circ \rho↓2$? 

\smallskip
\noindent{\bf Answer:} It is not. A common method to look for counterexamples
is to look for the simplest cases that fail. In this example, if any
of~$\rho↓1$, $X$, or~$\rho↓2$ is~$\emptyset$, the entire expression is~$\emptyset$,
so any counterexample will have at least one element in each. Try the
typical one-element case,
$$\rho↓1=\{\langle a,b\rangle\}\,,\quad X=\{c\}\,,\quad 
\rho↓2=\{\langle d,e\rangle\}\,.$$
Then the value of $\rho↓1\circ(X\circ \rho↓2)$ is
$$\vcenter{\halign{$\ctr{#}$&$\ctr{#}$&$\ctr{#}$\qquad&$\ctr{#}$\cr
&(c=d)&&c≠d\cr
\noalign{\medskip}
&\rho↓1\circ\{e\}&&\rho↓1\circ\emptyset=\emptyset\cr
\noalign{\medskip}
b=e&&b≠e\cr
\noalign{\medskip}
\{a\}&&\emptyset\cr}}$$
i.e., $\{a\}$ if $c=d$ and $b=e$, $\emptyset$ otherwise. By the same
reasoning, the value of $(\rho↓1\circ X)\circ \rho↓2$ is $\{e\}$ if $c=b$
and $a=d$. Letting $a=1$, $c=d=2$, $b=e=3$, we see
$\rho↓1\circ (X\circ \rho↓2)=\{1\}$,
$(\rho↓1\circ X)\circ \rho↓2=\emptyset$.
For this reason, we avoid writing sets between relations.

\smallskip
A relation $\rho$ is a {\it partial function\/} if $x\rho y$ and $x\rho z$
implies $y=z$; i.e., $\rho↑{-1}\circ\rho\subseteq \gamma$. A~relation is {\it total\/}
if for each~$x$ there is a~$y$ with $x\rho y$, i.e., $\gamma\subseteq \rho\circ
\rho↑{-1}$. A~relation has domain $\rho\circ U$, range $U\circ\rho$.

The identity relation is $\gamma=\{\,\langle x,x\rangle\mid x\in U\,\}$. 
$\gamma\circ\rho =\rho\circ \gamma=\rho$ for all~$\rho$. $\gamma↓s=\gamma\cap S\times S$.
The restriction of~$\rho$ to domain~$S$, range~$T$, is $\gamma↓s\circ 
\rho \circ \gamma↓T$.
$S\circ\rho\circ T=T\circ\rho↑{-1}\circ S$ (sets~$S$, $T$) defines $\rho↑{-1}$.

\smallskip
If $f$ is a function on domain $D$, and $X\subseteq D$, we extend $f$
to domain~$2↑D$ (subsets of~$D$)
by $f(X)=X\circ f=\{\,f(x)\mid x\in S\,\}$.
Similarly, if $f$ is a function $f(x,y)$ defined for $x\in D↓1$, $y\in D↓2$,
we extend $f$ to $x\in 2↑{D↓1}$, $y\in 2↑{D↓2}$, by
$f(X,Y)=\{\,f(x,y)\mid x\in X,y\in Y\,\}$.

In particular, if $X,Y\subseteq\Sigma↑{\ast}$, define {\it set concatenation\/}
$X\otimes Y=\{\,x\otimes y\mid x\in X, y\in Y\,\}$. Define the shuffle
of two sets of strings similarly. [RWF: define shuffle of individual
strings.]

If $X$ is a set, the {\sl regular sets\/} over $X$ are subsets of $X↑{\ast}$,
determined by:

\smallskip
\disleft 25pt:(1):
All finite subsets of $X↑{\ast}$ are regular.

\smallskip
\disleft 25pt:(2):
If $\rho↓1$ and $\rho↓2$ are regular, so are $\rho↓1\otimes \rho↓2$, 
$\rho↓1\cup \rho↓2$, and $\rho↓1↑{\ast}$.

\smallskip
If $X$ is an alphabet, we may write an expression to name each regular
set. Let ${\cal E}↓i$ be the expression that names~$\rho↓i$. If $\rho↓i$ is
finite, ${\cal E}↓i=\{a↓1,a↓2,\ldots,a↓n\}$, where each $a↓j\in \rho↓i$.
If $\rho↓1=\rho↓2\otimes \rho↓3$, ${\cal E}=({\cal E}↓2\otimes{\cal E}↓3)$.
If $\rho↓1=\rho↓2\cup \rho↓3$, ${\cal E}=({\cal E}↓2\cup{\cal E}↓3)$.
If $\rho↓1=\rho↓2↑{\ast}$, ${\cal E}={\cal E}↓2↑{\ast}$.
Traditionally $+$~is used instead of $\cup$, and the symbols $\{\,\}$,
$(\,)$, and $\otimes$ are often omitted where no confusion arises.
These expressions are the {\it regular expressions}.

\smallskip
\noindent{\bf Exercise:} Let $S↓M=\{\,x\in\Sigma↑{\ast}\mid M\hbox{ accepts }
\vdash x\dashv\,\}$, where $\vdash,\dashv\,\notin\Sigma$. Show $S↓M$
is regular. This shows that start and end markers are never needed 
for an $FA$ to recognize a language.

\smallskip
\noindent{\bf Proof:} $L↓M$, the set of strings $M$ accepts, is regular;
so is $\vdash\Sigma↑{\ast}\dashv$. Then their interection is regular,
and has a regular expression. Change $\vdash$ and $\dashv$ to $\Lambda$
wherever they appear in that expression to get a regular exprssion
for~$S↓M$. Does the end marker ever reduce the number of states needed?
Would it ever help to have a warning that the end of the input was drawing
near?

\vfill\eject
%\bigskip

A {\sl relation\/} $\rho$ {\it from\/} $S$ {\it to\/} $T$ 
is a two-place predicate with domain $S\times T$.
If $S=T$, we call $\rho$ a~relation {\sl on\/}~$S$. Normally, we write $u\rho v$ as
shorthand for $\rho(u,v)$. Familiar examples of relations are

$$\vcenter{\halign{$\ctr{#}$\quad&\lft{#}\quad&\lft{#}\cr
≤&&($S$ and $T$ the real numbers,\cr
&&or subsets thereof)\cr
\noalign{\smallskip}
=&&($S$ and $T$ can be any set)\cr
\noalign{\smallskip}
\subseteq&&($S$ and $T$ the power set of any set)\cr
\noalign{\smallskip}
\in&&($S$ any set, $T$ its power set)\cr
\noalign{\smallskip}
\equiv\,,\,\supset&&($S=T=\{\hbox{true},\hbox{false}\}$)\cr
\noalign{\smallskip}
|&(divides)&($S=$ the non-zero integers, $T=$ the integers)\cr
\noalign{\smallskip}
\approx&(is geometrically&($S=T=$ set of polygons)\cr
&congruent to)\cr
\noalign{\smallskip}
≡↓m&(differs by a multiple&($S=T=$ the integers)\cr
&of $m$ from)\cr
\tt{FATHER}&(short for&($S=T=$ the set of humans, living or dead)\cr
&``is the father of'')\cr
\hbox{\tt{MOTHER},}&(analogous)\cr
\hbox{\tt{BROTHER},}\cr
\hbox{\tt{WIFE}, etc.}\cr}}$$

\bigskip\noindent
The {\it converse\/} $\rho↑{-1}$ of such a relation is a relation from $T$ to~$S$,
where $v\rho↑{-1}u≡u\rho v$; converses of the relations above are respectively
$≥\,$, $=\,$, $\supseteq\,$, contains, $≡\,$, is implied by, is a multiple
of, $\approx\,$, $≡↓m\,$.

\smallskip
\disleft 38pt::
{\bf Drill:} What is the converse of {\tt WIFE}?

\smallskip
\disleft 38pt::
{\bf Drill:} Give a necessary and sufficient condition
for $\rho$ to be its own converse.

\smallskip
\disleft 38pt::
{\bf Answer:} $S=T$, $(\forall x,y)(x\rho y\supset y\rho x)$.
Such a relation is called {\sl symmetric\/}. 

\smallskip
The composition $\rho=\rho↓1\circ \rho↓2$ of $\rho↓1$ (from $S↓0$ to~$S↓1$) with
$\rho↓2$ (from $S↓1$ to~$S↓2$) is a relation from $S↓0$ to~$S↓2$ defined by
$$u\rho w≡(\exists v\in S↓1)(u\rho↓1v\wedge v\rho↓2w)\,.$$
For example, the relation ``{\tt NEPHEW}'' is 
$\hbox{\tt son}\circ\hbox{\tt sibling}$.

\smallskip
\disleft 38pt::
{\bf Drill:} Show $(\rho↓1\circ\rho↓2)↑{-1}=\rho↓2↑{-1}\circ\rho↓1↑{-1}$.

\smallskip
\disleft 38pt::
{\bf Answer:} 
$$\eqalign{u(\rho↓1\circ \rho↓2)↑{-1}v&≡v(\rho↓1\circ \rho↓2)u
≡(\exists w)(v\rho↓1w\wedge w\rho↓2u)\,;\cr
\noalign{\smallskip}
u(\rho↓2↑{-1}\circ \rho↓1↑{-1})v&≡(\exists w)(u\rho↓2↑{-1}w\wedge w\rho↓1↑{-1}v)≡
(\exists w)(w\rho↓2u\wedge v\rho↓1w)\,.\cr}$$

\smallskip
\disleft 38pt::
{\bf Drill:} Show $(\rho↓1\circ \rho↓2)\circ \rho↓3=\rho↓1\circ(\rho↓2\circ \rho↓3)$
(associativity of composition). This lets us write $\rho↓1\circ \rho↓2\circ \rho↓3$
without ambiguity.

\smallskip
Let $\gamma↓S$ be the relation (on any set containing $S$) $u\gamma↓Sv≡(u=v\in S)$.
If $S$ is the whole universe under consideration, we use~$\gamma$, omitting
the subscript. This is the same relation as $=\,$, but avoids such
notational confusions as $=\circ =↑{-1}$.

The identity relation in universe $U$ is the set of pairs $\gamma=\{\,\langle x,x\rangle
\mid x\in U\,\}$. The identity relation restricted to subset~$S$ is $S\times S\cap \gamma$.
The restriction of relation~$\rho$ to $\langle x,y\rangle$ such that
$x\in S$, $y\in T$, is $\gamma↓s\circ\rho\circ \gamma↓T$, also $(S\times T)\cap\rho$.

\smallskip
\noindent
Basic human relations:

Older is transitive and irreflexive:
$$\eqalign{{\rm Older}\circ{\rm Older}&\subseteq{\rm Older}\cr
{\rm Older}\cap \gamma&=\emptyset\,.\cr}$$

\noindent
Universe is People.

Everyone has exactly one mother and father; i.e., mother$↑{-1}$ and father$↑{-1}$
are total functions, mapping people into females and males respectively.
$$\eqalignno{{\rm mother}\circ{\rm mother}↑{-1}&\subseteq \gamma↓{\rm female}\,,\cr
{\rm father}\circ{\rm father}↑{-1}&\subseteq \gamma↓{\rm male}\,,\cr
\gamma&\subseteq{\rm mother}↑{-1}\circ{\rm mother}\cr
\gamma&\subseteq{\rm father}↑{-1}\circ{\rm father}\cr}$$
Therefore $\gamma=\gamma\circ \gamma\subseteq{\rm mother}↑{-1}\circ{\rm mother}
\circ{\rm mother}↑{-1}\circ{\rm mother}
\subseteq{\rm mother}↑{-1}\circ \gamma↓{\rm female}\circ{\rm mother}$)
$${\rm mother}\subseteq{\rm older}\,,\quad{\rm father}\subseteq{\rm older}\,.$$
(implies no ancestry loops)
$${\rm Male}{\cup\brace\cap}{\rm Female}={{\rm People}\brace\emptyset}
\,; \gamma↓{\rm male}{\cup\brace\cap}\gamma↓{\rm female}={\gamma↓{\rm people}\brace
\emptyset}\,.$$
\vskip-10pt
$$\eqalign{{\rm Parent}&={\rm father}\cup{\rm mother}\cr
{\rm Offspring}&={\rm father}↑{-1}\cup{\rm mother}↑{-1}={\rm parent}↑{-1}\cr
{\rm Son}&=\gamma↓{\rm male}\circ{\rm Offspring}\cr
&=({\rm Male}\times{\rm People})\cup{\rm Offspring}\cr
{\rm Brother}&=({\rm Son}\circ{\rm father})\cup({\rm Son}\circ{\rm mother})
\cup\overline{\gamma}\cr
{\rm Nephew}&=\gamma↓{\rm male}\circ{\rm Offspring}\circ{\rm Sibling}\cr
{\rm Ancestor}&={\rm Parent}↑+\cr
{\rm Descendant}&={\rm Offspring}↑+\cr}$$

\smallskip
\disleft 38pt::
{\bf Drill:} Define uncle in terms of father, mother, spouse, and male
$$\eqalign{{\rm Ancestor}↑{-1}&={\rm Descendant}\cr
{\rm Sibling}↑{-1}&={\rm Sibling}\cr}$$

If $\rho$ is a relation on $S$, define
$$\cases{\rho↑0=\gamma↓S\cr
\rho↑{i+1}=\rho↑i\circ\rho&if $i≥0$\cr
\rho↑{-(i+1)}=\rho↑{-1}\circ\rho↑{-1}&if $i≥1$\cr}$$
Note that when $i=0$, $\rho↑{-(i+1)}=\rho↑{-i}=\rho↑0\circ\rho↑{-1}=\rho↑{-i}
\circ\rho↑{-1}$.

\smallskip
\disleft 38pt::
{\bf Drill:} 
Show
$$\displaylines{\hbox{if }ij≥0,\ \rho↑i\circ\rho↑j=\rho↑{i+j}\cr
\rho↑{-i}=(\rho↑{-1})↑i\cr
\rho↑{\ast}=\bigcup↓{i≥0}\rho↑i\cr}$$

\smallskip
\disleft 38pt::
{\bf Drill:} 
Show $\rho↑i\circ\rho↑{-j}$ is not always $\rho↑{i-j}$.

\smallskip
If $\rho↓1$ and $\rho↓2$ are relations from $S$ to $T$, define $\rho=\rho↓1
\cup \rho↓2$ by 
$$u\rho v≡\bigl((u\rho↓1v)\vee (u\rho↓2v)\bigr)\,.$$
Similarly, if $\rho=\rho↓1\cap \rho↓2$,
$$u\rho v≡(u\rho↓1v\wedge u\rho↓2v)\,.$$

If $\{\rho↓i\}$ is a finite or infinite set  of relations,
$$\eqalign{\rho=\bigcup↓i\rho↓i&\quad\hbox{means}\quad u\rho v≡(\exists i)(u\rho↓iv)\cr
\noalign{\smallskip}
\rho=\bigcap↓i\rho↓i&\quad\hbox{means}\quad v\rho v≡(\forall i)(u\rho↓iv)\cr}$$

\smallskip
\disleft 38pt::
{\bf Drill:} Show 
$$\eqalign{(\rho↓1\cup \rho↓2)\cup \rho↓3&=\rho↓1\cup(\rho↓2\cup \rho↓3)\,,\cr
(\rho↓1\cap \rho↓2)\cap \rho↓3&=\rho↓1\cap(\rho↓2\cap \rho↓3)\,,\cr
\rho↓1\cap(\rho↓2\cup \rho↓3)&=(\rho↓1\cap \rho↓2)\cup(\rho↓1\cap \rho↓3)\,,\cr
\rho↓1\cup(\rho↓2\cap \rho↓3)&=(\rho↓1\cup \rho↓2)\cap(\rho↓1\cup \rho↓3)\,,\cr
\rho\cap\bigcup↓i\rho↓i&=\bigcup↓i(\rho\cap \rho↓i)\,,\cr
\rho\cup\bigcap↓i\rho↓i&=\bigcap↓i(\rho\cup \rho↓i)\,.\cr}$$

\smallskip
\disleft 38pt::
{\bf Answer:}
$$\eqalign{u\bigl((\rho↓1\cup \rho↓2)\cup \rho↓3\bigr)v&≡u(\rho↓1\cup \rho↓2)v\vee 
u\rho↓3v\cr
&≡\bigl((u\rho↓1v)\vee (u\rho↓2v)\bigr)\vee (u\rho↓3v)\cr
&≡(u\rho↓1v)\vee\bigl((u\rho↓2v)\vee(u\rho↓3v)\bigr)\,,\hbox{ etc.}\cr}$$

\smallskip
\noindent
If $\rho$ is a relation on $S$, $\rho↑{\ast}$ is defined as $\bigcup↓{i≥0}\rho↑i$,
and $\rho↑+$ is $\bigcup↓{i≥1}\rho↑i$.

Alternatively, define $\rho↑{\ast}$, the {\it iteration of\/}~$\rho$ by:

\smallskip
\display 30pt:i):
$\gamma\subseteq\rho↑{\ast}$; $\rho\subseteq\rho↑{\ast}$; $\rho↑{\ast}\circ
\rho↑{\ast}\subseteq\rho↑{\ast}$

\smallskip
\display 30pt:ii):
If $\gamma\subseteq\tau$, $\rho\subseteq\tau$, $\tau\circ\tau\subseteq\tau$.
then $\rho↑{\ast}\subseteq\tau$.

\smallskip
If there were two such $x↓1$ and $x↓2$, we would have $x↓1\subseteq x↓2
\subseteq x↓1$, so $x↓1=x↓2$. Yet another equivalent definition is
$\rho↑{\ast}=\bigcap\{\,\tau\mid\gamma\subseteq\tau,\,\rho\subseteq\tau,\,
\tau\circ\tau\subseteq\tau\,\}$.

\smallskip
\disleft 38pt::
{\bf Drill:} $\rho↑{\ast}=\gamma↓S\cup \rho↑+$, $\rho↑+=\rho\circ 
\rho↑{\ast}$, $\gamma↓S↑{\ast}=\gamma↓S$,
$(\rho\cup \rho↑i)↑{\ast}=\rho↑{\ast}$, $(\rho↑{\ast})↑{\ast}=\rho↑{\ast}$,
$\hbox{\tt PARENT}↑+=\hbox{\tt ANCESTOR}$, 
but not always $(\rho↑i)↑{\ast}=(\rho↑{\ast})↑i$.
If $\rho$ on the integers is $u\rho v≡(v=u+1)$, then $\rho↑{\ast}=$~``$≤$'' and
$\rho↑+=$~``$<$''.

\smallskip
A relation $\rho$ on $S$ is {\sl reflexive\/} if $(\forall u)(u\rho u)$, and
{\sl transitive\/} if $(u\rho v\wedge v\rho w)⊃(u\rho w)$. It is an
{\sl equivalence\/} (or RST) {\sl relation\/} if it is reflexive, symmetric,
and transitive. A~relation $\rho$ on~$S$ is {\it irreflexive\/} if
$\neg(\exists u)(u\rho u)$, and {\it intransitive\/} if 
$(u\rho v\wedge v\rho w)\supset\neg(u\rho w)$. Note that a relation
may be neither reflexive (transitive) nor irreflexive (intransitive).

%\vfill\eject

\smallskip
\disleft 38pt::
{\bf Drill:} Show $<\,$, $≤\,$, $\subseteq\,$, $\supset$ not transitive,
$\not \equiv$ intransitive. Show $≤$ reflexive, $<$ irreflexive. Show $=\,$,
$\approx\,$, $≡↓m$ are all equivalence relations.

\smallskip
If $\rho$ is an equivalence relation on $S$, we can break $S$ up into disjoint
subsets $S↓1,S↓2,S↓3,\ldots$ (finitely or infinitely many) where 
$u\rho v≡(u$ and $v$ are in the same~$S↓i)$. The $S↓i$ are called the
{\sl equivalence classes\/} of~$\rho$. Use $[u]↓{\rho}$ to mean the equivalence
class to which $u$ belongs.

\smallskip
\disleft 38pt::
{\bf Drill:} Show $(u\rho v)≡([u]↓{\rho}=[v]↓{\rho})$.
What are the equivalence classes of $≡↓2$?

\smallskip
If any set $S$ has a disjoint partition $\bigcup↓iS↓i$, show that there is an
equivalence relation $R$ on~$S$ of which the $S↓i$ are the equivalence classes.

\smallskip
\disleft 38pt::
\noindent{\bf Exercise.}
Show that, if $f$ is a function from set~$S$ to set~$T$, the relation
$\rho$ on~$S$ defined by $(x\rho y)\equiv \bigl(f(x)=f(y)\bigr)$ is an
equivalence relation. Conversely show that if $\rho$ is an equivalence
relation on a set~$S$, there is a set~$T$ and a function~$f$ from
$S$ to~$T$ such that $x\rho y$ if and only if $f(x)=f(y)$.

We may think of a relation $\rho$ from $S$ to $T$ as the set of
ordered pairs $\langle u,v\rangle$ for which $u\rho v$ is true.

\smallskip
\disleft 38pt::
{\bf Drill:} Show the previous definitions of $\rho↓1\cap \rho↓2$ and 
$\rho↓1\cup \rho↓2$
are consistent with this convention. Then $\emptyset$, the empty set,
is the always false relation; $u\emptyset v$ is false, $\emptyset\cap \rho=\emptyset$,
$\emptyset\cup \rho=\rho$. $S\times T$, as a relation from $S$ to~$T$, is always
true; $u(S\times T)v$ is true, $(S\times T)\cup \rho=S\times T$, 
$(S\times T)\cap \rho=\rho$. We can also say $\rho↓1\subseteq \rho↓2$ to mean
$u\rho↓1v⊃u\rho↓2v$.

\smallskip
\disleft 38pt::
{\bf Drill:} Show $(\rho↓1\subseteq \rho↓2)≡(\rho↓1\cap\rho↓2
=\rho↓1)≡(\rho↓1\cup \rho↓2=\rho↓2)$.

\smallskip
If $\rho$ is a relation from $S$ to $T$ and $p$ a property some relations have,
then the $p$-{\sl closure\/} of~$\rho$ is the smallest relation~$\rho'$ (if there
is one) such that $\rho\subseteq\rho'$ and $\rho'$ has property~$p$.
That is, $\rho'$ must include~$\rho$; it must have property~$p$; and it must
be a subset of any relation $\rho''$ that includes~$\rho$ and has property~$p$.
Note that a closure operation is idempotent:
$${\cal C}\bigl({\cal C}(\rho)\bigr)={\cal C}(\rho)\,.$$

The {\it reflexive closure\/} 
of $\rho$ on $S$ is $\rho\cup \gamma↓S$; the {\it symmetric closure\/}
is $\rho\cup\rho↑{-1}$; the {\it transitive closure\/} is~$\rho↑+$; 
the {\it reflexive transitive
closure\/} is~$\rho↑{\ast}$; the {\it equivalence (RST) closure\/} is $(\rho\cup 
\rho↑{-1})↑{\ast}$.

\smallskip
\disleft 38pt::
{\bf Drill:} Show the above.

\smallskip
Relations with finite domain and range may be displayed visually and stored
in a computer memory in several ways; for one, a table with rows indexed
by the elements of~$S$, columns by the elements of~$T$. The {\tt DIVIDES} relation,
on $(1:6)\times (0:8)$, is displayed by the table below:

$$\vbox{\tabskip=0pt\offinterlineskip
\halign{\rt{#}\quad&\vrule#&\strut\quad\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad
&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad
&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad&\vrule#\cr
&\omit&0&1&2&3&4&5&6&7&8&\omit\cr
&\multispan{11}\hrulefill\cr
&height2pt&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\cr
1&&X&X&X&X&X&X&X&X&X&\cr
2&&X&&X&&X&&X&&X&\cr
3&&X&&&X&&&X&&&\cr
4&&X&&&&X&&&&X&\cr
5&&X&&&&&X&&&&\cr
6&&X&&&&&&X&&&\cr
&height2pt&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\cr
&\multispan{11}\hrulefill\cr}}$$

\noindent
Such a table may be stored as a boolean array in a computer memory, and $uRv$
can be programmed as $R[u,v]$.

If $R$ is a relation on $S$, the table is square. If $R$ is reflexive, the
entire {\sl main diagonal\/} (from upper left to lower right) is marked;
if irreflexive, unmarked. If $R$ is symmetric, the table is symmetric around
the main diagonal. There is no simple visual test for transitivity. If
$R$ is an equivalence relation, the set $S$ can be placed in an order where
the marked regions of the table are squares covering the main diagonal:

$$\vbox{\tabskip=0pt\offinterlineskip
\halign{&\vrule#&\strut\quad\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad
&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad
&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad&\vrule#\cr
&\multispan{12}\hrulefill\cr
height2pt&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\cr
&&X&X&X&X&&&&&&&\cr
&&X&X&X&X&&&&&&&\cr
&&X&X&X&X&&&&&&&\cr
&&X&X&X&X&&&&&&&\cr
&&&&&&X&&&&&&\cr
&&&&&&&X&X&&&&\cr
&&&&&&&X&X&&&&\cr
&&&&&&&&&X&&&\cr
&&&&&&&&&&X&&\cr
height2pt&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\cr
&\multispan{12}\hrulefill\cr}}$$

\smallskip
\disleft 38pt::
{\bf Drill:} For which orderings of $S$ does the table take the form described?

\smallskip
A relation on $S$ may also be displayed as a {\sl directed graph\/} or
{\sl digraph}, a set~$S$ of {\sl nodes\/} and {\sl arcs}. The nodes are
normally shown as points,  small circles, boxes, or triangles. The
arcs, which are technically ordered pairs of nodes, are shown as arrows;
if $u\rho v$, there is an arrow from $u$ to~$v$. The nodes may be labeled with
their names. In such a graph, $u\rho↑{\ast}v$ iff there is a path from $u$
to $v$ following the arrows in their directions. If the relation is symmetric,
it is common to use a line without arrowheads between $u$ and~$v$ to show that
$u\rho v$; the digraph is then called a {\sl graph\/}, and the arcs {\sl edges\/}.

If a relation is reflexive, its digraph has {\sl loops\/}: arcs from each
node to itself.

It is possible to display several relations on $S$ in the same graph; each
arc is labeled with the name of the relation to which it belongs.

$$\vcenter{\halign{$\ctr{#}$\qquad&$\ctr{#}$\qquad&$\ctr{#}$\qquad
&$\ctr{#}$\qquad&$\ctr{#}$\qquad&$\ctr{#}$\qquad
&$\ctr{#}$\qquad&$\ctr{#}$\qquad&$\ctr{#}$\cr
&&<&&<&&<\cr
\noalign{\bigskip\bigskip}
&<&&<&&<&&<\cr
1&&2&&3&&4&&5\cr
\noalign{\bigskip\bigskip}
=&&=&&=&&=&&=\cr
\noalign{\bigskip\bigskip}
&&&<&&<\cr
\noalign{\bigskip\bigskip}
&&&&<\cr}}$$

\bigskip
We show the converse of a relation by reversing the arrows in its digraph.
We show its reflexive closure by filling in all loops.

\bigskip


%\bigskip
\noindent Paths in digraphs.
A {\sl path\/} from $q↓0$ to $q↓n$ is a sequence $\langle q↓0,x↓1,q↓1,\ldots,
x↓n,q↓n\rangle$ ($n≥0$) where $q↓{i-1}x↓iq↓i$ is an arc from $q↓{i-1}$ to~$q↓i$
labeled with~$x↓i$. 
The path is said to be {\sl labeled\/} with the concatenation
$x↓1x↓2\ldots x↓n$. The {\it null path\/} $\Lambda↓q$ from $q$ to~$q$ is the 
sequence~$\langle q\rangle$. The {\sl catenation\/} 
$p↓{qr}\aot p↓{rs}$ of a path $p↓{qr}$ from $q$ to~$r$ and a path $p↓{rs}$ from
$r$ to~$s$ is the concatenation $p↓{qr}\otimes\hbox{tail}(p↓{rs})$; notice
the elimination of the extra~$r$.

\smallskip
\disleft 38pt::
{\bf Drill:} Show $(p↓{qr}\aot p↓{rs})\aot p↓{st}=p↓{qr}\aot (p↓{rs}\aot p↓{st})$.
Show $p↓{qr}\aot \Lambda↓r=p↓{qr}$; $\Lambda↓q\aot p↓{qr}=p↓{qr}$.
Show if $p↓{qr}$ is labeled with~$x$, and $p↓{rs}$ is labeled with~$y$,
$p↓{qr}\aot p↓{rs}$ is labeled with~$xy$.

\smallskip
\disleft 38pt::
{\bf Drill:} If $p↓{qr}$ is a path from $q$ to $r$ in a multirelation graph,
and $p↓{qr}$ is labeled with~$x$, and $x=\langle R↓1,R↓2,\ldots,R↓n\rangle$,
then $q(R↓1\circ R↓2\circ \cdots\circ R↓n)r$.

Let $B\& b$ mean $B\cup\{b\}$, union with singleton set.

\vfill\eject

\smallskip\noindent
Kleene's Theorem:

The set of paths from $a$ via $B$ to~$c$:
$$\eqalign{S↓{a,\emptyset,a}&=\langle a\rangle\cup(\langle a,a\rangle\cap\rho)\cr
S↓{a,\emptyset,c}&=\langle a,c\rangle\cap\rho\quad\hbox{if }a≠c\cr
S↓{a,B\&b,c}&=S↓{a,B,c}\cup S↓{a,B,b}\circ S↑{\ast}↓{b,B,b}\circ S↓{b,B,c}\,.\cr}$$

\bigskip
\bigskip
$$\vcenter{\halign{$\hfil#\hfil$\qquad
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\cr
&&B\cr
\noalign{\bigskip}
&B&b&B\cr
\noalign{\bigskip}
a&&&&c\cr
\noalign{\bigskip}
&&B\cr}}$$
\bigskip
\bigskip
\nobreak
\centerline{``regular expressions''}

\noindent
Option: Omit $S↓{a,B,b}$ if $a=b$. (What else?)

By induction on $|B|$, $S↓{a,B,c}$ is expressible finitely in terms of paths
of length zero and one, $\emptyset$, $\cup\,$, $\circ\,$, and~$\ast$.
In $n↑3$ applications of the induction step, we get $S↓{a,\cup,b}$
for all $a,b$.

\bigskip
$$\vcenter{\halign{$\hfil#\hfil\;$&$\hfil#\hfil$\qquad\qquad
&$\hfil#\hfil\;$&$\hfil#\hfil$\qquad\qquad
&$\hfil#\hfil\;$&$\hfil#\hfil$\cr
x&\bullet&&&\bullet&y\cr
\noalign{\bigskip\bigskip}
\noalign{\bigskip\bigskip}
&&\bullet&z\cr}}$$

\bigskip
$$S↓{x\emptyset x}=\cases{\langle x\rangle\cr \langle xx\rangle}\,,\,
S↓{x\emptyset y}=\langle xy\rangle\,,\ldots\,,\,
S↓{xxx}=\langle x\rangle,\langle xx\rangle,\{\langle x\rangle,\langle x,x\rangle
\}\circ$$


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft July 2, 1984 

\vfill\eject

\noindent{\bf Course-of-Values Induction.}

\bigskip
To prove that a proposition $P(x)$ is true for all integers $x≥0$, a strategy
we may use is to assume $P(y)$ for {\sl any and all\/}~$y$ such that
$0≤y<x$, and prove $P(x)$ from this assumption. That is, we do not need
a separate basis step, and the induction step is allowed to assume not
just $P(x-1)$, but all of $P(0),P(1),P(2),\ldots,P(x-1)$. Nonetheless,
such a proof is valid, and is in fact a shorthand version of a proof by
ordinary mathematical induction. To see why, 
define $Q(x)$ to mean the conjunction $(\forall y\mid 0≤y<x)P(y)$. To
prove $Q(x)$ by induction on~$x$, we first prove the basis step,
$Q(0)≡(\forall y\mid 0≤y<0)P(y)$. Since there are no such values of~$y$,
the basis step is true whatever $P$ is. 

The induction step requires assuming $Q(x)≡(\forall y\mid 0≤y<x)P(y)$, and
proving $Q(x+1)≡(\forall y\mid 0≤y<x+1)P(y)$, i.e., 
$(\forall y\mid 0≤y≤x)P(y)$, i.e., $(\forall y\mid 0≤y<x)P(y)∧P(x)$.
The first conjuct is~$Q(x)$, so we need only prove $P(x)$
from $(\forall y\mid 0≤y<x)P(y)$, the course-of-values induction step.
This proves $\forall x\,Q(x)$, which implies $Q(x+1)$, which
implies~$P(x)$, which is what we wanted to do. The technique of
proving $P(x)$ by assuming $P(y)$ for all $y<x$ is called course-of-values
induction.

\bigskip
\noindent{\bf Example:} In the following, let $a,q,r\in{\bf N}$ and
$b\in{\bf N}↓+$.

If $a$ is an integer $≥0$, and $b>0$, there are unique numbers $q$ and~$r$
for which $a=bq+r$, $0≤r<b$. 

{\bf Case 1.} $a<b$. Then the only possibility is $q=0$, $r=a$.

{\bf Case 2.} $a≥b$. Let $a'=a-b≥0$. By course-of-values induction,
there are numbers $q'$, $r'$ with $a'=q'b+r'$, so $a=a'+b=(q'+1)b+r'$,
$q=q'+1$, $r=r'$.
If there were any other values $q''$, $r''$ with $a=bq''+r''$, we would
have $a'=a-b=b(q''-1)+r''$, contrary to the course-of-values induction
assumption that $q'=q-1$, $r'=r$ are unique.

\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft September 10, 1984

\vfill\eject
\line{\sevenrm OLD a57.tex[154,phy] \hfill}

\bigskip
\line{\bf Transitive Closures\hfill}

Let $\rho$ be a relation on~$S$. Define $R↑+$ as the intersection of all
relations~$T$ that both include~$R$ and are transitive. There is at least
one such relation, namely $T=S\times S$, so the intersection exists.
Because $R↑+$ is the intersection of relations all of which include~$R$,
$R\subset R↑+$. If $R↑+$ were not transitive, there would be $i$, $j$,
and~$k$ in~$S$ for which $iR↑+j$, $jR↑+k$, but not $iR↑+k$. Then there
must be some~$T$ for which $\neg iTk$, but $R↑+\subseteq T$, so $iTj$,
$jTk$, contradicting the transitivity of~$T$.

We want to show that $R↑+$ is the uniquely smallest addition to~$R$
(i.e., relation that includes~$R$) that is transitive. If $T$ is any
other, $T$~appears in the intersection that gives~$R↑+$, so $R↑+\subset T$,
and $T$~is not the smallest. We call $R↑+$ the {\sl transitive closure\/}
of~$R$.

The pattern of the above proof occurs repeatedly in mathematics; if you want
the smallest set with a certain property, and you suspect that there is
one set that is included in all the others having that property, try
taking the intersection of all the sets with property~$P$, and see if you
can prove it has the property. If you want the largest set that has a
certain property, take the union of all that have the property.

For example, if I want the smallest set that includes 6 and 15, and is
closed under subtraction, I~try the intersection of all such sets. One
such set is the set of multiples of three, so the intersection will only
contain multiples of three. All such sets contain $9=15-6$, and
$3=9-6$. If such a set contains~3, it contains $0=3-3$, $-3=0-3$,
$6=3-(-3)$, $9=6-(-3)$, etc., so the intersection contains all the
multiples of three. The intersection then is exactly the set of multiples
of three, and one more step ({\bf Drill:} What remains to prove?)
shows the intersection is what we were looking for.

If we want the smallest relation $R↑\ast$ that includes~$R$, and is
reflexive as well as transitive, we again try the intersection of all
such relations. 

{\bf Drill:} Show that the intersection has the required properties.

{\bf Drill:} What is the smallest equivalence relation that includes~$R$?

{\bf Drill:} Show by induction that $R↑i\subset R↑{\ast}$ for all $i≥0$.

{\bf Drill:} Show $\cup↓{i≥0}R↑i=R↑{\ast}$.
({\bf Answer:} From previous drill, $\cup↓{i≥0}R↑i\subset R↑{\ast}$. Because
$\cup↓{i≥0}R↑i$ is reflexive, transitive, and contains~$R$,
$R↑{\ast}\subset\cup↓{i≥0}R↑i$. So $R↑{\ast}=\cup↓{i≥0}R↑i$.)


\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd.
First draft (not published)
September 5, 1986.
%revised date;
%subsequently revised.

\bye